/**
 * @author Maximilian Csuk
 * @author Bernhard Denner
 * @author Konrad Paumann
 */
public class BinTree<K extends KeyType<K>> {
	
	
	private class Node {
		K key;
		int count;
		Node left;
		Node right;
		Node father;
		
		Node (K key) {
			this.key = key;
			count = 1;
			left = right = father = null;
		}
	}
	
	private Node root;
	
	public BinTree() {
		root = null;
	}
	
	
	public synchronized boolean insert(K key) {
		
		Node curr = null;
		Node currFather = null;
		
		if (root == null) {
				root = new Node(key);
				return true;
		}
		curr = root;
		while (curr != null) {
			if (key.equal(curr.key)) {	// key found -> inc counter
				curr.count++;
				return false;
			}
			
			currFather = curr;
			if (key.less(curr.key)) {	// key is smaller than currents node key
				curr = curr.left;
			} else {
				curr = curr.right;
			}
		}
		// key not found -> insert a new one
		if (key.less(currFather.key)) {
			currFather.left = new Node(key);
			currFather.left.father = currFather;
		} else {
			currFather.right = new Node(key);
			currFather.right.father = currFather;
		}
		return true;
	}
	
	/*
	 *  decrements the counter of the node with the given key
	 *  if counter is than lower than 1 the node is deleted
	 *  returns	0 if key wasn't found in the tree
	 *  		1 if counter of the node was decremented
	 *  		2 if node was deleted
	 */
	public synchronized byte delete(K key) {
		
		Node curr = root;
		Node toDelete = null;
		Node child = null;
		
		while (curr != null) {
			if (key.equal(curr.key)) {
				// key found -> delete it
				curr.count--;
				if (curr.count > 0) {
					return 1;
				}
					
				if (curr.left != null && curr.right != null) {
					toDelete = minimum(curr.right);			// current node has 2 childs
					curr.key = toDelete.key;
					curr.count = toDelete.count;
				} else {
					toDelete = curr;
				}
					
				// toDelete has max one child
				if (toDelete.left != null) {	// child = child of toDelete if it has one child 
					child = toDelete.left;
				} else {
					child = toDelete.right;		// otherwise null if toDelete has no child
				}
				if (child != null) {
					child.father = toDelete.father;
				}
				if (toDelete.father == null) {	// toDelete was root
					root = child;
				} else {
					if (toDelete == toDelete.father.left) {
						toDelete.father.left = child;
					} else {
						toDelete.father.right = child;
					}
				}
				return 2;
			}
			
			if (key.less(curr.key)) {
				curr = curr.left;
			} else {
				curr = curr.right;
			}
		}
		// key not found
		return 0;
	}
	
	/*
	 * returns the node with the smallest key of given tree
	 */
	private Node minimum(Node n) {
		if (n.left == null)
			return n;
		else {
			return minimum(n.left);
		}
	}
	
	public String toString() {
		if (root != null)
			return toStringr(root, "");
		else
			return "null";
	}
	
	private String toStringr(Node n, String s) {
		s += n.key + "(" + n.count + "), ";
		if (n.left != null) {
			s = toStringr(n.left, s);
		}
		if (n.right != null) {
			s = toStringr(n.right, s);
		}
		return s;
	}
}
